package com.lw.leetcode.arr.c;

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 902. 最大为 N 的数字组合
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/18 9:33
 */
public class AtMostNGivenDigitSet {

    public static void main(String[] args) {
        AtMostNGivenDigitSet test = new AtMostNGivenDigitSet();


        // 20
//        String[] arr = {"1", "3", "5", "7"};
//        int n = 100;

        // 218452
        String[] arr = {"1", "3", "5", "7"};
        int n = 465467348;

        // 29523
//        String[] arr = {"1", "4", "9"};
//        int n = 1000000000;

        // 1
//        String[] arr = {"7"};
//        int n = 8;

        int i = test.atMostNGivenDigitSet(arr, n);
        System.out.println(i);

    }

    public int atMostNGivenDigitSet(String[] digits, int n) {
        int[] arr = new int[10];
        int length = digits.length;
        String str = String.valueOf(n);
        int c = str.length();
        int sum = 0;
        int v = 1;
        int[] values = new int[c];
        values[0] = 1;
        for (int i = 1; i < c; i++) {
            v = v * length;
            values[i] = v;
            sum += v;
        }
        int item = 0;
        int st = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < length; i++) {
            int t = digits[i].charAt(0) - '0';
            set.add(t);
            for (int j = st; j < t; j++) {
                arr[j] = item;
            }
            st = t;
            item++;
        }
        for (int i = digits[length - 1].charAt(0) - '0'; i < 10; i++) {
            arr[i] = item;
        }
        int r = 0;
        for (int i = 0; i < c; i++) {
            int t = str.charAt(i) - '0';
            int a = arr[t];
            if (a > 0) {
                if (set.contains(t)) {
                    sum += (a - 1) * values[(c - 1 - i)];
                    r = 1;
                } else {
                    sum += a * values[(c - 1 - i)];
                    r = 0;
                    break;
                }
            } else {
                r = 0;
                break;
            }
        }
        sum += r;
        return sum;
    }

}
